A computer network typically comprises a plurality of interconnected devices, These devices include any network device, such as a server or end station, that transmits or receives data frames. A common type of computer network is a local area network (“LAN”) which typically refers to a privately owned network within a single building or campus. LANs may employ a data communication protocol, such as Ethernet or token ring, that defines the functions performed by the data link and physical layers of a communications architecture in the LAN. In many instances, several LANs are interconnected by point-to-point links, microwave transceivers, satellite hook-ups, etc. to form a wide area network (“WAN”), that may span an entire country or continent.
One or more intermediate network devices are often used to couple LANs together and allow the corresponding entities to exchange information. For example, a bridge may be used to provide a bridging function between two or more LANs. Alternatively, a switch may be utilized to provide a switching function for transferring information among a plurality of LANs or end stations. In effect, a switch is a bridge among more than 2 networks or entities. The terms “bridge” and “switch” will be used interchangeably throughout this description. Bridges and switches are typically devices that operate at the Data Link layer (“layer 2”) of the Open Systems Interconnection (“OSI”) model. Their operation is defined in the American National Standards Institute (“ANSI”) Institute of Electrical and Electronics Engineers (“IEEE”) 802.1D standard. A copy of the ANSI/IEEE Standard 802.1D, 1998 Edition, is incorporated by referenced herein in its entirety.
Telecommunication traffic among network devices is divided into seven layers under the OSI model and the layers themselves split into two groups. The upper four layers are used whenever a message passes to or from a user. The lower three layers are used when any message passes through the host computer, whereas messages intended for the receiving computer pass to the upper four layers. “Layer 2” refers to the data-link layer, which provides synchronization for the physical level and furnishes transmission protocol knowledge and management.
Networks may be designed using a plurality of distinct topologies—that is the entities in the network may be coupled together in many different ways. Referring to FIGS. 1-3, there is shown different examples of “ring” topologies. A ring topology is a network configuration formed when “Layer 2” bridges are placed in a circular fashion with each bridge having two and only two ports belonging to a specific ring. FIG. 1 shows a single ring 50 having bridges 52 connected by paths 54. Each bridge 52 in ring 50 in FIG. 1 has two ports 52a and 52b belonging to the ring. FIG. 2 shows two adjacent rings, 50a and 50b, with a single bridge 56 having two ports 56a, 56b belonging to each ring.
In FIGS. 1 and 2, no paths or bridges are shared among rings. In FIG. 3 two rings 50c and 50d are connected and share two bridges 58, 60. Bridge 58 has two ports 58a and 58b which each uniquely belong to only one ring, rings 50c and 50d respectively. Bridge 58 also has one port 58c connected to a path which is shared by both rings 50c and 50d. If rings are assigned different priority levels, a port such as 58c connected to the shared link assumes the priority value of the higher priority ring, and ports 58a and 58b in shared bridge 58 and port 60a in bridge 60 connected to the lower priority ring are deemed to be customer (or lower priority) ports. The use of a shared link between shared bridges 58, 60 allows for the connection of rings and the growth of a larger network from smaller ring components; however, the shared link also presents difficulties since its failure affects both rings 50c and 50d. 
Ring topologies shown in FIGS. 1-3 present Layer 2 traffic looping problems. As illustrated in FIG. 4, in a single ring topology, data traffic can circulate around in either direction past their origination and thus create repetition of messages. For example, data traffic may originate in bridge 51, travel counter-clockwise in the ring, pass bridge 57 and return to bridge 51; this is called a loop. Loops are highly undesirable because data frames may traverse the loops indefinitely. Furthermore, because switches and bridges replicate (i.e., flood) frames whose destination port is unknown or which are directed to broadcast or multicast addresses, the existence of loops may cause a proliferation of data frames that effectively overwhelms the network.
To prevent looping, one of the paths in the ring is blocked, as shown in FIG. 4, by blocking data traffic in one of the ring ports—in this case, either port 51a or 57a. The port is deemed to be in a “blocking” state, in which it does not learn or forward incoming or outgoing traffic.
A network may be segregated into a series of logical network segments. For example, any number of physical ports of a particular switch may be associated with any number of other ports by using a virtual local area network (“VLAN”) arrangement that virtually associates the ports with a particular VLAN designation. Multiple ports may thus form a VLAN even though other ports may be physically disposed between these ports.
The VLAN designation for each local port is stored in a memory portion of the switch such that every time a message is received by the switch on a local port the VLAN designation of that port is associated with the message. Association is accomplished by a flow processing element which looks up the VLAN designation in the memory portion based on the local port where the message originated.
Most networks include redundant communications paths so that a failure of any given link or device does not isolate any portion of the network. For example, in the ring networks shown in FIGS. 1-4, if communication is blocked preventing data from flowing counter-clockwise, the data may still reach its destination by moving counter-clockwise. The existence of redundant links, however, may also cause the formation of loops within the network.
To avoid the formation of loops, many network devices execute a “spanning tree algorithm” that allows the network devices to calculate an active network topology which is loop-free (e.g. has a needed number of ports blocked) and yet connects every element in every VLAN within the network. The IEEE 802.1D standard defines a spanning tree protocol (“STP”) to be executed by 802.1D compatible devices (e.g., bridges, switches, and so forth). In the STP, Bridge Protocol Data Units (“BPDUs”) are sent around the network and are used to calculate the loop free network technology.
Other available protocols include that shown and described in now pending NETWORK CONFIGURATION PROTOCOL AND METHOD FOR RAPID TRAFFIC RECOVERY AND LOOP AVOIDANCE IN RING TOPOLOGIES, filed Mar. 4, 2002, Ser. No. 10/090,669 and now pending SYSTEM AND METHOD FOR PROVIDING NETWORK ROUTE REDUNDANCY ACROSS LAYER 2 DEVICES, filed Apr. 16, 2002, Ser. No. 10/124,449. The entirety of these applications are hereby incorporated by reference.
All of the current protocols require devices in a network to be protocol-aware. That is, each device must be able to run and understand the protocol that is globally running in the network. A misconfigured protocol or malfunctioning device could potentially cause a loop that would impact the whole network.
To illustrate this problem, referring to FIG. 5, there is shown a network 80 comprising a core or higher priority network such as a provider 70 coupled to a customer or lower priority network 72 through a switch 74. Core network 70 runs a conventional spanning tree protocol to avoid loops and has defined a blocked path 76. This means that either port 78 or port 80 is blocked. Many different causes may result in involuntary loops which may collapse the entire network 80 including: STP corrupted BPDUs, unidirectional optical fibers which result, for example, when paths which typically comprise two fibers but one has shut down, and non-configured protocols in loop topologies. In the example in FIG. 5, someone in customer network 72 has improperly disabled the STP running in network 72 or, the STP has become disabled due to problems just mentioned. As a consequence, even though core network 70 is properly running the STP to avoid loops, since the customer in network 72 is not running the STP, a loop is created in customer network 72 and packets from customer network 72 flood core network 70. As core network 70 and customer network 72 share the same data domain, core network 70 will be flooded with customer packets and will be affected adversely by the customer's action. Yet, it is not possible to ensure that all network administrators or devices are properly doing their respective jobs and running respective STPs.
Therefore, there is a need in the art for a system and method which can detect and isolate remote loops created in another network.